﻿#define _CRT_SECURE_NO_WARNINGS 1

#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>
#include <algorithm>

using namespace std;

//最长连续递增序列
class Solution
{
public:
    int findLengthOfLCIS(vector<int>& nums)
    {
        int n = nums.size(), ret = 0;
        for (int i = 0; i < n;)
        {
            int j = i + 1;
            // 找到递增区间的末端
            while (j < n && nums[j] > nums[j - 1]) j++;
            ret = max(ret, j - i);
            // 直接在循环中更新下⼀个位置的起点
            i = j;
        }

        return ret;
    }
};

//买卖股票的最佳时机
class Solution
{
public:
    int maxProfit(vector<int>& prices)
    {
        // 在数组中找两个数差的最大值
        // 固定最后一个数,找出前面的最小值
        // 固定下一个数的之后，前面的最小值为上一个位置与上一个位置前面的最值的最小值
        // minprice表示卖出之前的价格的最小值
        int n = prices.size(), minprice = INT_MAX;
        int ret = 0;
        for (int i = 0; i < n; i++)
        {
            // 需要先更新结果，在更新最小值
            ret = max(ret, prices[i] - minprice);
            minprice = min(minprice, prices[i]);
        }

        return ret;
    }
};

//买卖股票的最佳时机II
class Solution
{
public:
    int maxProfit(vector<int>& prices)
    {
        // 将天数和当天的价格画为二维坐标系中发现是一个折线
        // 我们只需要计算每个上升折线的差值即可
        int n = prices.size(), ret = 0;
        for (int i = 0; i < n;)
        {
            int j = i;
            // 找上升的末端
            while (j + 1 < n && prices[j + 1] > prices[j]) j++;
            ret += prices[j] - prices[i];
            i = j + 1;
        }

        return ret;
    }
};

class Solution
{
public:
    int maxProfit(vector<int>& prices)
    {
        // 只要后一天的价格比前一天的价格高,就加入最终值
        int n = prices.size(), ret = 0;
        for (int i = 1; i < n; i++)
        {
            if (prices[i] > prices[i - 1])
                ret += prices[i] - prices[i - 1];
        }

        return ret;
    }
};

//K次取反后最大化的数组和
class Solution
{
public:
    int largestSumAfterKNegations(vector<int>& nums, int k)
    {
        // 分为三种情况:k小于负数的个数,只需要从小到大的k个数变为相反数即可
        // k == 负数的个数,则把所以的负数取反
        // k 大于负数的个数,则先将所有的负数取反,
        // 如果负数的个数(m - k )为偶数则忽略即可
        // 如果为奇数，则将现在的数组的最小数变为相反数
        // 1.统计负数的个数以及绝对值最小的数
        int m = 0, minelem = INT_MAX;
        for (auto x : nums)
        {
            if (x < 0) m++;
            minelem = min(minelem, abs(x));
        }

        int ret = 0;
        // 负数的个数大于k
        if (m > k)
        {
            sort(nums.begin(), nums.end());
            for (int i = 0; i < k; i++)
                ret += abs(nums[i]);
            for (int i = k; i < nums.size(); i++)
                ret += nums[i];
        }
        else
        {
            for (auto x : nums)
                ret += abs(x);
            if ((m - k) % 2)
                ret -= minelem * 2;
        }

        return ret;
    }
};
int main()
{
	return 0;
}